#include<iostream>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    long long climbStairs(int n) {
        //dp[i] = dp[i-1] + dp[i-2]。
        if(n==1)
            return 1;
        long long pre=1,now=1,temp;
        for(int i=2;i<=n;i++) {
            temp = now;
            now = pre+now;
            pre = temp;
        }
        return now;
    }
};
int main(int argc, char** argv){
    Solution *s = new Solution();
    int result;
    result = s->climbStairs(4);
    cout << "[" << result << "]" << endl;
    return 0;
}